package com.kevin.Code.String;

/**
 * @author Vinlee Xiao
 * @Classname MultiplyStrings
 * @Description Leetcode 43. 字符串相乘 中等难度
 * @Date 2021/11/2 15:54
 * @Version 1.0
 */
public class MultiplyStrings {

    /**
     * 自己思路 击败人数较少
     * 做法简单 但是注意的细节较多
     *
     * @param num1
     * @param num2
     * @return
     */
    public String multiply(String num1, String num2) {

        if (num1.charAt(0) == '0' || num2.charAt(0) == '0') {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();

        //声明字符串数组
        char[] chars1;
        char[] chars2;

        //默认num1的长度大于num2
        if (len1 >= len2) {
            chars1 = num1.toCharArray();
            chars2 = num2.toCharArray();
        } else {
            chars1 = num2.toCharArray();
            chars2 = num1.toCharArray();
        }

        //最终的结果
        StringBuilder finalResult = new StringBuilder();
        StringBuilder result = new StringBuilder();


        for (int i = len2 - 1; i >= 0; i--) {
            //用于保留每一次 单个数字相乘的结果
            StringBuilder temp = new StringBuilder();
            //num2的单个数字
            int n1 = chars2[i] - '0';
//                System.out.println("n1:"+n1);
            //进位
            int carry = 0;
            //余留的数
            int reminder = 0;
            //前面增加0
            for (int k = len2 - 1 - i; k > 0; k--) {
                temp.append(0);
            }
            //计算num2中每个数与num1中的乘积
            for (int j = len1 - 1; j >= 0; j--) {
                //表示向前的进位
                //增加0的个数

                int n2 = chars1[j] - '0';
                int mulNum = n1 * n2;
                reminder = (mulNum + carry) % 10;
                carry = (mulNum + carry) / 10;
                temp.append(reminder);
            }

            //是否产生进位
            if (carry != 0) {
                temp.append(carry);
            }
//                System.out.println(temp);
            //final result
            if (finalResult.length() == 0) {
                finalResult.append(temp);
            }

            //tmp 和final 两个相加的字符串
            if (i < len2 - 1) {

                finalResult = add1(finalResult, temp);
            }
            //重新清空
            temp = new StringBuilder();
        }
        //第三步对字符串进行翻转
        for (int i = finalResult.length() - 1; i >= 0; i--) {
            result.append(finalResult.charAt(i));
        }

        return result.toString();
    }

    /**
     * 实现两个字符串的相加
     *
     * @param tmp1
     * @param tmp2
     * @return
     */
    public StringBuilder add(StringBuilder tmp1, StringBuilder tmp2) {

        int left = 0;
        int len1 = tmp1.length();
        int len2 = tmp2.length();
        int min = Math.min(len1, len2);

        int carry = 0;
        int reminder = 0;
        StringBuilder result = new StringBuilder();

        while (left < min) {
            int m1 = tmp1.charAt(left) - '0';
            int m2 = tmp2.charAt(left) - '0';

            reminder = (m1 + m2 + carry) % 10;
            carry = (m1 + m2 + carry) / 10;

            result.append(reminder);
            left++;
        }

        while (left < len1) {

            int m1 = tmp1.charAt(left) - '0';
            reminder = (m1 + carry) % 10;
            carry = (m1 + carry) / 10;
            result.append(reminder);
            left++;
        }

        while (left < len2) {

            int m1 = tmp2.charAt(left) - '0';
            reminder = (m1 + carry) % 10;
            carry = (m1 + carry) / 10;
            result.append(reminder);
            left++;
        }
        if (carry != 0) {
            result.append(carry);
        }
        //翻转


        return result;
    }

    /**
     * @param tmp1
     * @param tmp2
     * @return
     */
    public StringBuilder add1(StringBuilder tmp1, StringBuilder tmp2) {

        //进位
        int carry = 0;
        int index = 0;
        int len1 = tmp1.length();
        int len2 = tmp2.length();
        int reminder = 0;
        StringBuilder result = new StringBuilder();

        while (index < len1 || index < len2 || carry != 0) {

            int m1 = index >= len1 ? 0 : tmp1.charAt(index) - '0';
            int m2 = index >= len2 ? 0 : tmp2.charAt(index) - '0';

            int temp = m1 + m2 + carry;
            reminder = temp % 10;
            carry = temp / 10;
            result.append(reminder);
            index++;
        }

        return result;
    }


    public static void main(String[] args) {

        MultiplyStrings multiplyStrings = new MultiplyStrings();
        String s = multiplyStrings.multiply("123", "456");
        System.out.println(s);

    }
}
